package main

import (
	"fmt"
	"go-study/algorithm/standard"
	"math"
)

// 如何求一棵二叉树的最大子树和
// 给定一棵二叉树，它的每个节点都是正整数或负整数
// 如何找到一棵子树，使得它所有节点的和最大

func main() {
	root := createTree()
	findMaxSubTree(root)
	fmt.Println("最大子树和为：", maxSum)
	fmt.Println("对应子树的根节点为：", maxRoot.Data)
}

var maxSum = math.MinInt64
var maxRoot *standard.BNode

func findMaxSubTree(root *standard.BNode) int {
	if root == nil {
		return 0
	}

	lMax := findMaxSubTree(root.LeftChild)
	rMax := findMaxSubTree(root.RightChild)
	sum := lMax + rMax + root.Data.(int)
	if sum > maxSum {
		maxSum = sum
		maxRoot = root
	}
	return sum
}

func createTree() *standard.BNode {
	root := &standard.BNode{}
	node1 := &standard.BNode{}
	node2 := &standard.BNode{}
	node3 := &standard.BNode{}
	node4 := &standard.BNode{}

	root.Data = 6
	node1.Data = 3
	node2.Data = -7
	node3.Data = -1
	node4.Data = 9

	root.LeftChild = node1
	root.RightChild = node2
	node1.LeftChild = node3
	node1.RightChild = node4

	return root
}
